538. 把二叉搜索树转换为累加树

Similar Question

leading to the advanced question

Solution Tips

方案一: DFS

var convertBST = function(root) {
    // 中序遍历+前缀和即可
    // 因为是所有小的会累加, 还是个逆序中序遍历
    let preSum = 0;
    function dfs(node) {
        if (node === null) return 0;

        dfs(node.right);
        preSum += node.val;
        node.val = preSum;
        dfs(node.left);
    }

    dfs(root);
    return root;
};

减少全局变量

var convertBST = function(root) {
    // 中序遍历+前缀和即可
    // 因为是所有小的会累加, 还是个逆序中序遍历
    function dfs(node, preSum) {
        if (node === null) return 0;
        node.val += dfs(node.right, preSum)
        return dfs(node.left, node.val);
    }

    dfs(root);
    return root;
};